#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

int PartitionPivot(int * T, int g,int d,int pivot){
  int * Aux= new int[d-g+1];
  int 	i =0;  int j = d-g;
  for (int k =  g; k<=d; k++){
    if( T[k] < pivot){
      Aux[i] = T[k];
      i++;
    }
    else if (T[k] > pivot){
      Aux[j] = T[k];
      j--;
    }
  }
  for(int l = i ; l<=j; l++){
    Aux[l] = pivot;
  }
  for(int z =g; z <=d; z++){
    T[z] = Aux[z-g];
  }
  delete [] Aux;
  return i+g;
}

void QuickSort(int * tab, int g, int d){
  if (d>g){
    int pivot = tab[g+ rand()%(d-g)];
    int pos_pivot = PartitionPivot(tab,g,d,pivot);
    QuickSort(tab,g,pos_pivot-1);
    QuickSort(tab,pos_pivot+1,d);
  }
}

bool check(int * t, int taille){
  for (int i =0 ; i < taille-1; i++){
    if (t[i] > t[i+1]){
      return false;
    }
  }
  return true;
}

int main(){
  srand(time(NULL));
  int taille = 64000;
  int * tab= new int[taille];
  int i=0;
  for ( i=0; i< taille; i++){
    tab[i] = rand()%10;
  }
  cout<<"init"<<endl;
  time_t t1,t2;
  t1 = clock();
  QuickSort(tab,0,taille-1);
  t2 = clock();
  for(int z= 0 ; z<taille;z++){
    cout<<tab[z]<<endl;
  }
  cout<<"Check : "<<check(tab,taille)<<endl;
  cout<<"Time : "<<(t2-t1)/CLOCKS_PER_SEC<<endl;
  

 return 0 ;
}
